<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="style.css" type="text/css">
<meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type">
<link rel="Start" href="index.html">
<link rel="previous" href="BitSet.html">
<link rel="next" href="DynArray.html">
<link rel="Up" href="index.html">
<link title="Index of types" rel=Appendix href="index_types.html">
<link title="Index of exceptions" rel=Appendix href="index_exceptions.html">
<link title="Index of values" rel=Appendix href="index_values.html">
<link title="Index of class methods" rel=Appendix href="index_methods.html">
<link title="Index of classes" rel=Appendix href="index_classes.html">
<link title="Index of modules" rel=Appendix href="index_modules.html">
<link title="Base64" rel="Chapter" href="Base64.html">
<link title="BitSet" rel="Chapter" href="BitSet.html">
<link title="Dllist" rel="Chapter" href="Dllist.html">
<link title="DynArray" rel="Chapter" href="DynArray.html">
<link title="Enum" rel="Chapter" href="Enum.html">
<link title="ExtArray" rel="Chapter" href="ExtArray.html">
<link title="ExtHashtbl" rel="Chapter" href="ExtHashtbl.html">
<link title="ExtLib" rel="Chapter" href="ExtLib.html">
<link title="ExtList" rel="Chapter" href="ExtList.html">
<link title="ExtString" rel="Chapter" href="ExtString.html">
<link title="Global" rel="Chapter" href="Global.html">
<link title="IO" rel="Chapter" href="IO.html">
<link title="OptParse" rel="Chapter" href="OptParse.html">
<link title="Option" rel="Chapter" href="Option.html">
<link title="PMap" rel="Chapter" href="PMap.html">
<link title="RefList" rel="Chapter" href="RefList.html">
<link title="Std" rel="Chapter" href="Std.html">
<link title="UChar" rel="Chapter" href="UChar.html">
<link title="UTF8" rel="Chapter" href="UTF8.html">
<link title="Unzip" rel="Chapter" href="Unzip.html"><link title="node functions " rel="Section" href="#6_nodefunctions">
<link title="list conversion " rel="Section" href="#6_listconversion">
<link title="enums " rel="Section" href="#6_enums">
<title>Dllist</title>
</head>
<body>
<div class="navbar"><a class="pre" href="BitSet.html" title="BitSet">Previous</a>
&nbsp;<a class="up" href="index.html" title="Index">Up</a>
&nbsp;<a class="post" href="DynArray.html" title="DynArray">Next</a>
</div>
<h1>Module <a href="type_Dllist.html">Dllist</a></h1>
<pre><span class="keyword">module</span> Dllist: <code class="code">sig</code> <a href="Dllist.html">..</a> <code class="code">end</code></pre><div class="info">
A mutable, imperative, circular, doubly linked list library
<p>

    This module implements a doubly linked list in a mutable or imperitive
    style (changes to the list are visible to all copies of the list).<br>
</div>
<hr width="100%">
<pre><span id="TYPEnode_t"><span class="keyword">type</span> <code class="type">'a</code> node_t</span> </pre>

<pre><span id="EXCEPTIONEmpty"><span class="keyword">exception</span> Empty</span></pre>
<br>
<h6 id="6_nodefunctions">node functions </h6><br>
<pre><span id="VALcreate"><span class="keyword">val</span> create</span> : <code class="type">'a -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Creates a node.  This is an O(1) operation.<br>
</div>
<pre><span id="VALcopy"><span class="keyword">val</span> copy</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Copy the list attached to the given node and return the copy of the given
    node.  This is an O(N) operation.<br>
</div>
<pre><span id="VALlength"><span class="keyword">val</span> length</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> int</code></pre><div class="info">
Returns the length of the list.  This is an O(N) operation.<br>
</div>
<pre><span id="VALrev"><span class="keyword">val</span> rev</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info">
List reversal.  This is an O(N) operation.<br>
</div>
<pre><span id="VALadd"><span class="keyword">val</span> add</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a -> unit</code></pre><div class="info">
<code class="code">add n a</code> Creates a new node containing data <code class="code">a</code> and inserts it into
    the list after node <code class="code">n</code>.  This is an O(1) operation.<br>
</div>
<pre><span id="VALappend"><span class="keyword">val</span> append</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
<code class="code">append n a</code> Creates a new node containing data <code class="code">a</code> and inserts it into
    the list after node <code class="code">n</code>. Returns new node.  This is an O(1) operation.<br>
</div>
<pre><span id="VALprepend"><span class="keyword">val</span> prepend</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
<code class="code">prepend n a</code> Creates a new node containing data <code class="code">a</code> and inserts it into
    the list before node <code class="code">n</code>. Returns new node.  This is an O(1) operation.<br>
</div>
<pre><span id="VALpromote"><span class="keyword">val</span> promote</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info">
<code class="code">promote n</code> Swaps <code class="code">n</code> with <code class="code">next n</code>.  This is an O(1) operation.<br>
</div>
<pre><span id="VALdemote"><span class="keyword">val</span> demote</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info">
<code class="code">demote n</code> Swaps <code class="code">n</code> with <code class="code">prev n</code>.  This is an O(1) operation.<br>
</div>
<pre><span id="VALremove"><span class="keyword">val</span> remove</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info">
Remove node from the list no matter where it is.  This is an O(1) operation.<br>
</div>
<pre><span id="VALdrop"><span class="keyword">val</span> drop</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Remove node from the list no matter where it is. Return next node.  This is
    an O(1) operation.<br>
</div>
<pre><span id="VALrev_drop"><span class="keyword">val</span> rev_drop</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Remove node from the list no matter where it is. Return previous node.  This
    is an O(1) operation.<br>
</div>
<pre><span id="VALsplice"><span class="keyword">val</span> splice</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info">
<code class="code">splice n1 n2</code> Connects <code class="code">n1</code> and <code class="code">n2</code> so that
    <code class="code">next n1 == n2 &amp;&amp; prev n2 == n1</code>. This can be used to connect two discrete
    lists, or, if used on two nodes within the same list, it can be used to
    separate the nodes between <code class="code">n1</code> and <code class="code">n2</code> from the rest of the list. In this
    case, those nodes become a discrete list by themselves.  This is an O(1)
    operation.<br>
</div>
<pre><span id="VALget"><span class="keyword">val</span> get</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a</code></pre><div class="info">
Given a node, get the data associated with that node.  This is an
    O(1) operation.<br>
</div>
<pre><span id="VALset"><span class="keyword">val</span> set</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a -> unit</code></pre><div class="info">
Given a node, set the data associated with that node.  This is an O(1)
    operation.<br>
</div>
<pre><span id="VALnext"><span class="keyword">val</span> next</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Given a node, get the next element in the list after the node.  
<p>

    The list is circular, so the last node of the list returns the first 
    node of the list as it's next node.
<p>

    This is an O(1) operation.<br>
</div>
<pre><span id="VALprev"><span class="keyword">val</span> prev</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Given a node, get the previous element in the list before the node.
<p>

    The list is circular, so the first node of the list returns the
    last element of the list as it's previous node.
<p>

    This is an O(1) operation.<br>
</div>
<pre><span id="VALskip"><span class="keyword">val</span> skip</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> int -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
<code class="code">skip n i</code> Return the node that is <code class="code">i</code> nodes after node <code class="code">n</code> in the list.
    If <code class="code">i</code> is negative then return the node that is <code class="code">i</code> nodes before node <code class="code">n</code>
    in the list.  This is an O(N) operation.<br>
</div>
<pre><span id="VALiter"><span class="keyword">val</span> iter</span> : <code class="type">('a -> unit) -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> unit</code></pre><div class="info">
<code class="code">iter f n</code> Apply <code class="code">f</code> to every element in the list, starting at <code class="code">n</code>.  This
    is an O(N) operation.<br>
</div>
<pre><span id="VALfold_left"><span class="keyword">val</span> fold_left</span> : <code class="type">('a -> 'b -> 'a) -> 'a -> 'b <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a</code></pre><div class="info">
Accumulate a value over the entire list.  
    This works like List.fold_left. This is an O(N) operation.<br>
</div>
<pre><span id="VALfold_right"><span class="keyword">val</span> fold_right</span> : <code class="type">('a -> 'b -> 'b) -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'b -> 'b</code></pre><div class="info">
Accumulate a value over the entire list.
    This works like List.fold_right, but since the list is bidirectional,
    it doesn't suffer the performance problems of List.fold_right.
    This is an O(N) operation.<br>
</div>
<pre><span id="VALmap"><span class="keyword">val</span> map</span> : <code class="type">('a -> 'b) -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'b <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Allocate a new list, with entirely new nodes, whose values are
    the transforms of the values of the original list.  Note that this
    does not modify the given list.  This is an O(N) operation.<br>
</div>
<br>
<h6 id="6_listconversion">list conversion </h6><br>
<pre><span id="VALto_list"><span class="keyword">val</span> to_list</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a list</code></pre><div class="info">
Converts a dllist to a normal list.  This is an O(N) operation.<br>
</div>
<pre><span id="VALof_list"><span class="keyword">val</span> of_list</span> : <code class="type">'a list -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Converts from a normal list to a Dllist and returns the first node. Raises
    <code class="code">Empty</code> if given list is empty.  This is an O(N) operation.<br>
</div>
<br>
<h6 id="6_enums">enums </h6><br>
<pre><span id="VALenum"><span class="keyword">val</span> enum</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a <a href="Enum.html#TYPEt">Enum.t</a></code></pre><div class="info">
Create an enum of the list.
    Note that modifying the list while the enum exists will have undefined
    effects.  This is an O(1) operation.<br>
</div>
<pre><span id="VALrev_enum"><span class="keyword">val</span> rev_enum</span> : <code class="type">'a <a href="Dllist.html#TYPEnode_t">node_t</a> -> 'a <a href="Enum.html#TYPEt">Enum.t</a></code></pre><div class="info">
Create a reverse enum of the list.
    Note that modifying the list while the enum exists will have undefined
    effects.  This is an O(1) operation.<br>
</div>
<pre><span id="VALof_enum"><span class="keyword">val</span> of_enum</span> : <code class="type">'a <a href="Enum.html#TYPEt">Enum.t</a> -> 'a <a href="Dllist.html#TYPEnode_t">node_t</a></code></pre><div class="info">
Create a dllist from an enum.
    This consumes the enum, and allocates a whole new dllist. Raises
    <code class="code">Empty</code> if given enum is empty.  This is an O(N) operation.<br>
</div>
</body></html>